package com.lw.leetcode.linked;

/**
 * @Author liw
 * @Date 2021/5/14 10:50
 * @Version 1.0
 */
public class SplitListToParts {
    public ListNode[] splitListToParts(ListNode root, int k) {
        int n = 0;
        ListNode item = root;
        while (item != null) {
            n++;
            item = item.next;
        }
        int mod = n % k;
        int size = n / k;
        ListNode[] arr = new ListNode[k];
        item = root;
        for (int i = 0; i < k && item != null; i++) {
            int limit = size + (i < mod ? -1 : 0);
            arr[i] = item;
            for (int j = 0; j < limit; j++) {
                item = item.next;
            }
            ListNode node = item.next;
            item.next = null;
            item = node;
        }
        return arr;
    }

    public ListNode[] splitListToParts1(ListNode root, int k) {
        int n = 0;
        ListNode cur = root;
        while (cur != null) {
            n++;
            cur = cur.next;
        }
        int mod = n % k;
        int size = n / k;
        ListNode[] res = new ListNode[k];
        cur = root;
        for (int i = 0; i < k && cur != null; i++) {
            res[i] = cur;
            int cursize = size + (mod-- > 0 ? 1 : 0);
            for (int j = 0; j < cursize - 1; j++) {
                cur = cur.next;
            }
            ListNode next = cur.next;
            cur.next = null;
            cur = next;
        }
        return res;
    }
}
